The present invention relates generally to the field of computer graphics and in particular to a method for iteratively extracting layers from a current set of primitives in order to render the primitives in an order, which can be front-to-back or back-to-front.
One of the earliest, if not the earliest, solutions to computing a visibility-order, which is the basis for several recent techniques starts with a rough ordering in z (depth) of the primitives. Then for each primitive, the algorithm fine tunes the ordering by checking whether other primitives actually precede it in the ordering.
The BSP-tree, which is a data structure that represents a hierarchical convex decomposition of a given space, was then developed. Each node v of a BSP-tree T corresponds to a convex polyhedral region, P(v)  R3; the root node corresponds to all of R3. Each non-leaf node v also corresponds to a plane, h(v), which partitions P(v) into two subregions, P(v+)=h+(v)#P(v) and P(vxe2x88x92)=hxe2x88x92(v)∩P(v), corresponding to the two children, v+ and vxe2x88x92 of v. Here, h+(v) (respectively, hxe2x88x92(v)) is the half-space of points above (respectively, below) plane h(v). It was demonstrated that BSP-trees can be used for obtaining a visibility ordering of a set of objects (or, more precisely, an ordering of the fragments into which the objects are cut by the partitioning planes). The key observation is that the structure of the BSP-tree permits a simple recursive algorithm for xe2x80x9cpaintingxe2x80x9d the object fragments from back to front: If the viewpoint lies in, say, the positive half-space h+(v), then (recursively) the fragments stored in the leaves of the sub-tree rooted at vxe2x88x92 are painted first, then the object fragments S(v)  h(v), and then (recursively) the fragments stored in the leaves of the sub-tree rooted at v+.
It is important to note that the BSP-tree does not actually generate a visibility order for the original primitives, but for fragments of them. It has been shown how to recover the visibility order from the sorted fragments. There are a few issues in using BSP-trees for visibility-ordering. Building a BSP-tree is a computationally intensive process. Thus, handling dynamic geometry is a challenge. Using techniques from the field of xe2x80x9ckineticxe2x80x9ddata structures, an efficient extension of BSP-trees for handling moving primitives was developed. At this time, this technique requires xc3xa1 priori (actual analytical) knowledge of the motion of the geometry to efficiently perform local changes on the BSP-tree as the primitives move.
Another technique for visibility order, wherein a well-chosen (small) set of ray shooting queries are performed, is known. The ray shooting queries compute for each primitive (at least) its successor and predecessor in the visibility ordering. By running a topological sort on these pair-wise relations, it is possible to recover a visibility order. One of the shortcomings of this technique is that it might actually obtain a larger portion of the visibility graph than necessary to compute the ordering. Since the ray shooting queries are relatively expensive both in time and memory, this can be inefficient.
An incremental visibility sorting: algorithm has also been presented, similar in some respects to the algorithm using a rough ordering in z (depth) and then fine tuning the ordering. This algorithm, despite having a worst case running time of O(n4), is shown to be quite fast in practice. In order to cull the number of visibility relations that need to be maintained, several optimizations, such as the use of kd-trees (hierarchical data decomposition trees) and the tracking of overlaps of the convex hulls of the geometric primitives are performed. Their algorithm is able to explore temporal coherency and, in fact, is optimized for dynamic geometry. This algorithm also proposes a technique for correct rendering in the presence of cycles.
Another related technique is known, which uses a multi-pass rendering technique with a xe2x80x9cmovingxe2x80x9d depth buffer to render transparent objects.
Building complicated data structures to solve the visibility-ordering problem is a fairly difficult task. Given that interactivity is of utmost importance in most applications, it would be prudent to try and solve this problem in hardware at some pre-specified resolution. As other researchers have found exploiting the ever-faster graphics hardware available in workstations and PCs, can lead to simpler, and more efficient solutions to rendering problems. The present invention is motivated by this trend.
The initial motivation for the present invention comes from volume rendering, but the present invention has other applications, which include image-based rendering acceleration, animations with selective display, efficient rendering with transparency. The main contribution of the present invention is a method for computing a visibility ordering of a set of (acyclic) primitives by using features of the graphics hardware.
The present invention is, therefore, a hardware-assisted visibility ordering algorithm. From a given viewpoint, a (back-to-front) visibility ordering of a set of objects is a partial order on the objects such that if object A obstructs object B, then B precedes A in the ordering. Note, however, if the visibility ordering is front-to-back then if object A obstructs B, then B precedes A in the ordering and B less than p A. Such orderings are useful because they are the building blocks of other rendering algorithms such as direct volume rendering of unstructured grids. The conventional way to compute the visibility order is to build a set of visibility relations (e.g., B less than p A), and then run a topological sort on the set of relations to actually get the partial ordering. The present invention instead works by assigning a layer number to each primitive, which directly determines the visibility ordering. Objects that have the same layer number are independent, and have no obstruction between each other. A method, which exploits a combination of the zxe2x88x92 and stencil buffers to compute the layer number of each primitive, is used. One application of the method of the present invention is to obtain a fast unstructured volume rendering algorithm. In an exemplary embodiment the present invention is implemented in OpenGL as well as described in terms of pseudo code.
Most conventional visibility ordering algorithms first build a sufficient set of pair-wise visibility relations (e.g., B less than p A), and then in a second phase, a topological sort is needed on the set of relations to actually obtain the ordering. Sufficiency for the present invention is in the sense that it is possible to extend such pair-wise relations into a valid partial order. The technique of the present invention instead works by assigning a layer number to each primitive, which directly determines the visibility ordering. To compute the layer number of each primitive, extensive use is made of the graphics hardware. In particular, a combination of the zxe2x88x92 and stencil buffers is exploited.
It is, therefore, an object of the present invention to iteratively extract layers from a set of primitives using programmable hardware in order to render the primitives.
It is a further object of the present invention to use a subdivision scheme to avoid unnecessary reading and scanning of the data.